package leetcode.code1008;

import leetcode.helper.tree.TreeNode;

public class Solution {
	public TreeNode bstFromPreorder(int[] preorder) {
		return build(preorder, 0, preorder.length - 1);
	}

	private TreeNode build(int[] preorder, int L, int R) {
		if (L > R) {
			return null;
		}
		TreeNode cur = new TreeNode(preorder[L]);
		if (L == R) {
			return cur;
		}
		int r = L + 1;
		while (r <= R && preorder[r] < preorder[L]) {
			r++;
		}
		cur.left = this.build(preorder, L + 1, r - 1);
		cur.right = this.build(preorder, r, R);
		return cur;
	}
}
